The invention relates to channel utilization enhancements for long and variable delay channels, such as channel utilization enhancements for TCP (Transport Control Protocol) over high-speed wireless channels.
The utilization of a channel, for example during a bulk data transfer, is determined by the balance between the capacity of the channel and the amount of data available to feed into that channel. This balance needs to be managed. If the balance is in favor of the capacity, under-utilization occurs. If the balance is in favor of the amount of data put in transit, optimal utilization is achieved. However, for channels with a variable capacity, there will be excessive packets that may have to be either buffered or dropped, as they will not be accommodated by the transmission channel when the capacity shrinks periodically.
This is particularly true for high-speed third generation (3G) wireless communications systems where one of the major issues in effectively transporting packet data using Internet protocols such as TCP/IP (Transport Control Protocol/Internet Protocol) is such an under-utilization of allocated high-speed radio channels. This is a significant issue since such radio channels are scarce resources due to the fundamental limit on the available radio spectrum. In high-speed 3G wireless environments, a high-speed channel results in a larger bandwidth delay product which is enlarged further by the length and variable delay characteristics of such channels.
The channel capacity of a TCP connection is the product of channel bandwidth and the round trip delay and is a measure of the volume of the xe2x80x9cpipexe2x80x9d between the end-hosts. A longer round trip delay increases the capacity and therefore will demand more data onto the channel such that the pipe can be filled. A higher channel speed also allows the channel to accommodate more packets, and will also require the server host to send data more quickly as the pipe empties faster. When a link has long and variable delay the channel capacity will increase, and will also be variable.
Over a wireless link, high error rates may exist (compared with those on fixed wire-line links) and despite various coding techniques these error rates may still translate into a high radio frame erasure rate (typically, 10%), which in turn translates into more than a 10% packet loss for data transfer rates of 64-144-384 kbps. For this reason, link layer retransmissions are employed to compensate for this high frame erasure rate. Typically an Automatic Repeat Request (ARQ) based method is used such as RLP-III (Radio Link Protocol-III). These retransmissions of course contribute to the size and variability of the delay. There is an accumulative delay per retransmission as the frame is inserted into the current transmission stream. Furthermore, a lost frame cannot be released to upper layers until it is retransmitted correctly. If the retransmission protocol provides in-order data delivery, frames will be put off on the receiving side by the lost frame in front of them. These frames will have to wait for the correct retransmission before being released. The residual frame error may be reduced, e.g., to below 0.2% with 2-4 retransmissions for a resulting packet loss of around 1%. These retransmissions extend the one-way delay by 160-320 ms. Such delays only occur when the initial frame is lost, they are variable to TCP/IP, and are proportional to the frame error rate of the link.
These delays will interact with TCP to produce a number of effects with the end result that under-utilization of the channel occurs. Firstly, retransmissions will delay the forwarding of effected packets to the TCP/IP layers. Retransmissions will also push back all the packets closely following each effected packet during the retransmission. Secondly, the corresponding TCP client-to-server direction acknowledgements for all the effected packets will experience delay. The server will wait for the duration of the delay before sending data because TCP uses these acknowledgements to regulate the data flow from the server to the client. Thirdly, if the acknowledgements do not arrive at the TCP server host, it will not transmit new data onto the channel, creating periods of idling of the channel. This will result in under-utilization and also stretch the overall TCP session time. Fourthly, delayed acknowledgement implementation of TCP and possible loss and retransmission of acknowledgements in the client-to-server direction will also contribute to under-utilization.
FIG. 1 illustrates an example delay characteristic experienced by packets to be sent between a wire-line end-host 10 and a mobile end-host 12. The plot shows a relatively stable delay region 14 for a wire-line portion of the link, and a variable delay region 16 shown by the fluctuating plot lines for a wireless portion of the link.
The impact of stable delay on utilization will be described with reference to FIG. 2 so that it may be contrasted with the impact of variable delay which is described below with reference to FIG. 3. A TCP end-to-end packet flow pattern is plotted in FIG. 2 where the round trip delay is stable for example for communication between a first wire-line host 10 and a second wire-line host 18. After TCP completes slow-start, the congestion window and the received advertised window size limits the server to send data in packet bunches corresponding to the size of the client advertised window size. Given a large enough delay of the channel or a high channel speed, TCP utilization of the channel will degrade.
The operations of TCP proceed as follows. Assuming TCP flow control has completed slow-start, the first wire-line host 10 fills in the channel with the maximum number of packets allowed by the minimum of congestion window, the received advertised window size, and the sender""s retransmission buffer size. It will wait for the first client-to-server direction ACK packet to come back from the second wire-line host 18 before sending more data. The waiting period becomes one of the root causes of channel under-utilization as soon as synchronization between the number of packets sent and the round trip delay is disrupted. In FIG. 2, t is the size of the packet in time; T is the round trip time of the channel from the time the first of the packets is sent until the corresponding ACK is received; n is the number of packets that will be sent as dictated by the smallest of the congestion window size, the received advertised window size, and the sender""s buffer size. For the channel to be fully utilized to the total of the bandwidth and delay product, the following equation must hold: Txe2x89xa7nxc2x7t.
When T greater than nxc2x7t, there is an idle time; xe2x80x9cIxe2x80x9d in the radio channel. I equates to the time between when the current full window of packets have been transmitted and the next window of packets triggered by the reception of ACKs for those packets. As this pattern of packet transmission is repeated the overall channel utilization is reduced by I=Txe2x88x92nxc2x7t, or as a percentage of reduced utilization U=(Txe2x88x92nxc2x7t)/T. The relationship of T and t can be illustrated by the relative difference between channel speed and the overall delay. With a T greater than  greater than t, which can be either interpreted as long delay of the network, or high data rate channel, even a large n will still cause an idle time I. n=T/t can be achieved by enlarging the joint effect of the TCP congestion window, the received advertised window size, and the sender""s buffer size. With a higher channel speed (and/or longer overall network delay), a larger n is required to reduce I, thus to achieve a lower U. For such a channel, an n1 can be calculated such that if applied, it can allow TCP flow control to fill in the idle time I of the channel and increase utilization to (near) the optimum.
The impact of variable delay will be described with reference to FIG. 3. As stated previously, variable delay can be caused by link layer retransmissions. For high speed 3G wireless channels, a higher frame error rate is expected. The link layer will retransmit the lost frames both in client-to-server and server-to-client directions. It may take several round trip times across the wireless channel to retransmit a lost frame, each of which adds delay. As these retransmission delays occur only for frames that are effected, these delays are variable proportionally to the frame erasure rate of the link. Regardless of how the variable delay may be caused, TCP will interact with these variable delays. Similar to FIG. 2, there will be an idle time I1 in the event T1 greater than nxc2x7t if it is indeed the case as in FIG. 3 representing the stable component of the delay. V2 and V3 are variable delays in the server-to-client direction and client-to-server direction respectively. Now the round trip delay for the variable delay channel is T2=T1+V2+V3 which is increased and is no longer a (near) constant, resulting in a different idle time I2=I1+V2+V3. Therefore for the delay of T2 a different n2 will have to be applied for optimal utilization. This situation will be much more complex as the adjustment of n will have to be dynamic as a function of the changing T.
Techniques such as xe2x80x9cexplicit window adaptationxe2x80x9d algorithms have been proposed to reduce the amount of data available for transmission. They reduce the TCP received advertised window size, but do not maintain their own buffer. They suppress the amount of data from the TCP server host. Although they are effective when a network node is experiencing congestion, they may actually be harmful when the problem is channel under-utilization.
Techniques using various TCP proxies exist which split a TCP connection. These proxies terminate the TCP connection from one end-host and originate a separate connection to the other host. The second TCP connection may be optimized for particular link such as the wireless channel. This breaks the TCP end-to-end semantics in that a packet may be acknowledged before the end-host has actually received it.
Some methods simply enlarge the absolute size of the TCP receiver buffer. Enlarging the receiver buffer can allow TCP to send more data onto the channel. However, these methods will require modifications to the TCP/IP protocol stack, the OS, or the application configurations on TCP end-hosts. Furthermore, as packets converge to a relatively small and frequently variable channel, packets may have to be dropped or buffered.
It is an object of the invention to obviate or mitigate one or more of the above-identified disadvantages.
The invention provides systems and methods which allow the under-utilization of high-speed radio channels to be reduced significantly. Advantageously, there is only a small associated cost, and only a small increase in processing power and buffer space in the radio access network infrastructure.
Embodiments of the invention provide various dynamic rate control (DRC) systems and methods through packet queuing and queue management for a specific link segment of the end-to-end connection. In TCP embodiments, DRC may transparently use the client advertised window size mechanism provided within TCP to maintain a steady stream of packets to be transported onto a channel having a dynamically changing capacity due to a highly variable delay.
DRC provides for a steady, but not excessive amount of packets in its queue. This queue is managed by dynamically relating the current size of the queue to the amount of incoming data by enlarging or shrinking the client advertised window size to the predicted queue growth.
DRC does not perform end-to-end flow control, but rather it supplements this function of TCP. The invention may be implemented as an agent of TCP in the sense that it is hidden in the middle of the network. While various flavors of TCP adapt to the end-to-end conditions of the packet flow, the invention enhances this by adapting to the conditions of a particular link segment, e.g., a high-speed 3G wireless channel. In performing this function, DRC requires no changes or enhancements to current TCP/IP protocols; it can co-operate with all TCP/IP flavors.
DRC may be implemented in a manner which avoids end-host modifications by managing packet queuing in the middle of the end-to-end TCP connection and still achieves the improvement in utilization. To the extent that DRC is able to maintain the packet queue efficiently it does not need to drop packets. In this regard it differs from the previously discussed solutions in which the receive buffer is simply enlarged.
DRC maintains the integrity of the end-to-end TCP connection, and maintains TCP semantics in that it will not acknowledge a packet until the receiver acknowledges it. In this regard, it differs from the previously discussed TCP proxy solutions which split a TCP connection into two parts.
According to one broad aspect, the invention provides a method of requesting packets from a first end-point for transmission to a second end-point over a first channel followed by a second channel which is a wireless channel having a dynamically changing capacity due to a highly variable delay. The method is implemented at an interface between the first and second channels. Packets received on the first channel are queued in a queue having a queue length equal to the number of packets queued, and are dequeued onto the second channel as capacity of the second channel permits. An estimate is made which is directly or indirectly representative of the instantaneous capacity of the second channel. As a function of the queue length and the estimate, transmissions are requested from the first end-point in a manner which avoids the queue becoming empty when the first end-point still has further packets to transmit.
The invention may be applied in the context of an end-to-end packet delivery system in which the first end-host is permitted to send packets as a function of a window size specified in acknowledgement packets it receives. In this case the method further includes receiving acknowledgement packets over the second channel. For each acknowledgement packet received, an original window size specified in the acknowledgement packet received is extracted, a new window size is calculated as a function of the queue length, the estimate and the window size, and a new acknowledgement packet is generated which is substantially the same as the acknowledgement packet received except that the new window size has been substituted in place of the original window size. Packet transmissions from the first end-point are then requested by forwarding the acknowledgement packet on the first channel.